package leetcode.editor.cn;

import java.awt.geom.Ellipse2D;
import java.util.Scanner;

/**
题目名字---:合并两个有序链表
题目编号---:21	
解题时间---:2021-12-02 08:20:20
*/

public class MergeTwoSortedLists{
    public static void main(String[] args) {
        Solution solution = new MergeTwoSortedLists().new Solution();
        ListNode list1 = createList();
        System.out.println("第一个链表创建完毕");
        ListNode list2 = createList();
        solution.mergeTwoLists(list1,list2);
    }
    public static ListNode createList() {
        ListNode head = new ListNode();
        ListNode curr = head;
        Scanner scanner = new Scanner(System.in);
        int input;
        System.out.println("请输入:");
        input  = scanner.nextInt();
        while (input!=-1) {
            ListNode node = new ListNode(input);
            curr.next = node;
            curr = curr.next;
            System.out.println("请输入:");
            input = scanner.nextInt();
        }
        return head.next;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode curr = new ListNode();
        ListNode head = curr;
        while (list1!=null||list2!=null)  {
            if (list1==null&&list2!=null) {
                curr.next = list2;
                list2 = list2.next;
                curr =curr.next;
            }
            if (list2==null&&list1!=null) {
                curr.next = list1;
                curr =curr.next;
                list1 = list1.next;
            }
            if (list1!=null&&list2!=null) {
                if (list1.val> list2.val) {
                    curr.next =  list2;
                    curr = curr.next;
                    list2 = list2.next;
                }else {
                    curr.next =  list1;
                    curr = curr.next;
                    list1 = list1.next;
                }
            }
        }
        curr.next = null;
        return head.next;
    }
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        ListNode curr =  head;
        while (list1!=null&&list2!=null) {
            if (list1.val> list2.val) {
                curr.next = list2;
                list2 = list2.next;
            }else {
                curr.next =  list1;
                list1 =  list1.next;
            }
            curr = curr.next;
        }
        //可能有一个链表此时为空
        curr.next = list1 == null ? list2: list1;
        curr.next = null;
        return head.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
}

class ListNode {
 int val;
   ListNode next;
 ListNode() {}
     ListNode(int val) { this.val = val; }
 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
